package solution.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * @author : wenchao.long
 * @date : Created in 2024-07-04 下午 11:24 周四
 * @description :
 * 		<a href="https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked">最长连续序列</a>
 * 		<p>
 * 		给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 		请你设计并实现时间复杂度为 O(n) 的算法解决此问题
 * 		</p>
 */
public class No128 {

	public static int longestConsecutive(int[] nums) {
		Set<Integer> set = new HashSet<>();

		for (int num : nums) {
			set.add(num);
		}

		int maxLength = 0;

		for (int num : nums) {
			// 如果序列中 不包含 当前num的下一位 往前推看下 num + 1在不在队列，如果不在队列 证明当前num的最长队列为1
			if (!set.contains(num - 1)) {
				int currentNum = num;
				int currentLength = 1;

				while (set.contains(currentNum + 1)) {
					currentLength++;
					currentNum++;
				}

				maxLength = Math.max(maxLength, currentLength);
			}
		}

		return maxLength;
	}

	public static void main(String[] args) {
		System.out.println(longestConsecutive(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
	}
}
